{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Height of Special Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: heightOfTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #特殊二叉树的高度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一棵具有 <code>n</code> 个节点的 <strong>特殊</strong> 二叉树的根节点 <code>root</code> 。特殊二叉树的节点编号从 <code>1</code> 到 <code>n</code> 。假设这棵树有 <code>k</code> 个叶子，顺序如下：<code>b<sub>1</sub> &lt; b<sub>2</sub> &lt; ... &lt; b<sub>k</sub></code> 。</p>\n",
    "\n",
    "<p>这棵树的叶子节点有一个 <strong>特殊</strong> 属性 ！对于每个叶子节点 <code>b<sub>i</sub></code> ，满足以下条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>i &lt; k</code> ，则 <code>b<sub>i</sub></code> 的右子节点为 <code>b<sub>i&nbsp;</sub><sub>+ 1</sub></code> ；否则为 <code>b<sub>1</sub></code> 。</li>\n",
    "\t<li>如果 <code>i &gt; 1</code> ，则 <code>b<sub>i</sub></code> 的左子节点为 <code>b<sub>i&nbsp;</sub><sub>- 1</sub></code> ；否则为 <code>b<sub>k</sub></code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回给定树的高度。</p>\n",
    "\n",
    "<p><strong>注意</strong>：二叉树的高度是指从根节点到任何其他节点的 <strong>最长路径</strong> 的长度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1;</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>root = [1,2,3,null,null,4,5]\n",
    "<b>输出：</b>2\n",
    "<strong>解释：给</strong>定树如下图所示。每个叶子节点的左子节点是它左边的叶子节点（用蓝色边表示）。每个叶子节点的右子节点是它右边的叶子节点（用红色边表示）。我们可以看出，该图的高度为2。\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/07/12/1.png\" style=\"padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 200px; height: 200px;\" /></p>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>root = [1,2]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>给定树如下图所示。只有一个叶子节点，所以它没有左子节点或右子节点。我们可以看出，该图的高度为 1。\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/07/12/2.png\" style=\"padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 95px; height: 122px;\" /></p>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>root = [1,2,3,null,null,4,null,5,6]\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>给定树如下图所示。每个叶子节点的左子节点是它左边的叶子节点（用蓝色边表示）。每个叶子节点的右子节点是它右边的叶子节点（用红色边表示）。我们可以看出，该图的高度为3。\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/07/12/3.png\" style=\"padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 200px; height: 280px;\" /></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n 为树中节点的数量</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= node.val &lt;= n</code></li>\n",
    "\t<li>输入保证每个 <code>node.val</code> 的值是唯一的。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [height-of-special-binary-tree](https://leetcode.cn/problems/height-of-special-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [height-of-special-binary-tree](https://leetcode.cn/problems/height-of-special-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,null,null,4,5]', '[1,2]', '[1,2,3,null,null,4,null,5,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def heightOfTree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(node, dpt):\n",
    "            nonlocal ans\n",
    "            ans = max(ans, dpt)\n",
    "            if node.left and node.left.right is not node:\n",
    "                dfs(node.left, dpt+1)\n",
    "            if node.right and node.right.left is not node:\n",
    "                dfs(node.right, dpt+1)\n",
    "        \n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightOfTree(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        def dfs(node,dpt):\n",
    "            nonlocal ans\n",
    "            ans = max(ans,dpt)\n",
    "            if node.left and node.left.right is not node:\n",
    "                dfs(node.left,dpt+1)\n",
    "            if node.right and node.right.left is not node:\n",
    "                dfs(node.right,dpt+1)\n",
    "        dfs(root,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def heightOfTree(self, root: Optional[TreeNode]) -> int:\n",
    "        # 每一个叶子节点还能有左右孩子\n",
    "        # 如果他能被多次访问到就是叶子\n",
    "        rec = set() # 记录是第几次被访问\n",
    "        leaves = set() # 记录是否是叶子\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return \n",
    "            if node.val in rec:\n",
    "                leaves.add(node.val)\n",
    "                return \n",
    "            rec.add(node.val)\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        \n",
    "        ans = 0\n",
    "        def getDepth(node, d):\n",
    "            nonlocal ans \n",
    "            if not node:\n",
    "                return\n",
    "            if node.val in leaves: # 是叶子节点更新逻辑\n",
    "                ans = max(ans, d)\n",
    "                return \n",
    "            getDepth(node.left,d + 1)\n",
    "            getDepth(node.right, d + 1)\n",
    "        getDepth(root, 0)\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def heightOfTree(self, root: Optional[TreeNode]) -> int:\n",
    "        # 每一个叶子节点还能有左右孩子\n",
    "        # 如果他能被多次访问到就是叶子\n",
    "        rec = set() # 记录是第几次被访问\n",
    "        leaves = set() # 记录是否是叶子\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return \n",
    "            if node.val in rec:\n",
    "                leaves.add(node.val)\n",
    "                return \n",
    "            rec.add(node.val)\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        \n",
    "        ans = 0\n",
    "        def getDepth(node, d):\n",
    "            nonlocal ans \n",
    "            if not node:\n",
    "                return\n",
    "            if node.val in leaves: # 是叶子节点更新逻辑\n",
    "                ans = max(ans, d)\n",
    "                return \n",
    "            getDepth(node.left,d + 1)\n",
    "            getDepth(node.right, d + 1)\n",
    "        getDepth(root, 0)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # 读题\n",
    "    def heightOfTree(self, root: Optional[TreeNode]) -> int:\n",
    "        # 每一个叶子节点还能有左右孩子\n",
    "        # 如果他能被多次访问到就是叶子\n",
    "        rec = set() # 记录是第几次被访问\n",
    "        leaves = set() # 记录是否是叶子\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            if node.val in rec:\n",
    "                leaves.add(node.val)\n",
    "                return \n",
    "\n",
    "            rec.add(node.val)\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "        def getDepth(node, d):\n",
    "            nonlocal ans \n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            if node.val in leaves: # 是叶子节点更新逻辑\n",
    "                ans = max(ans, d)\n",
    "                return\n",
    "\n",
    "            getDepth(node.left, d + 1)\n",
    "            getDepth(node.right, d + 1)\n",
    "\n",
    "\n",
    "        getDepth(root, 0)\n",
    "            \n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # # dfs\n",
    "    # 读题 叶节点彼此之间是左右节点的环\n",
    "    # 这棵树的叶子节点有一个 特殊 属性 ！对于每个叶子节点 bi ，满足以下条件：\n",
    "    # 如果 i < k ，则 bi 的右子节点为 bi + 1 ；否则为 b1 。\n",
    "    # 如果 i > 1 ，则 bi 的左子节点为 bi - 1 ；否则为 bk 。\n",
    "    def heightOfTree(self, root: Optional[TreeNode]) -> int:\n",
    "        # 每一个叶子节点还能有左右孩子\n",
    "        # 如果他能被多次访问到就是叶子\n",
    "        rec = set() # 记录是第几次被访问\n",
    "        leaves = set() # 记录是否是叶子\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            if node.val in rec:\n",
    "                leaves.add(node.val)\n",
    "                return \n",
    "\n",
    "            rec.add(node.val)\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "        def getDepth(node, d):\n",
    "            nonlocal ans \n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            if node.val in leaves: # 是叶子节点更新逻辑\n",
    "                ans = max(ans, d)\n",
    "                return\n",
    "\n",
    "            getDepth(node.left, d + 1)\n",
    "            getDepth(node.right, d + 1)\n",
    "\n",
    "\n",
    "        getDepth(root, 0)\n",
    "            \n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "from typing import Optional\n",
    "\n",
    "class Solution:\n",
    "    def heightOfTree(self, root: Optional[TreeNode]) -> int:\n",
    "        rec = set()  # 记录是第几次被访问\n",
    "        leaves = set()  # 记录是否是叶子\n",
    "        \n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            if node.val in rec:\n",
    "                leaves.add(node.val)\n",
    "                return\n",
    "            rec.add(node.val)\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "            \n",
    "        dfs(root)\n",
    "        \n",
    "        ans = 0\n",
    "        \n",
    "        def getDepth(node, d):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return\n",
    "            if node.val in leaves:  # 是叶子节点更新逻辑\n",
    "                ans = max(ans, d)\n",
    "                return\n",
    "            getDepth(node.left, d + 1)\n",
    "            getDepth(node.right, d + 1)\n",
    "            \n",
    "        getDepth(root, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def heightOfTree(self, root: Optional[TreeNode]) -> int:\n",
    "        # 每一个叶子节点还能有左右孩子\n",
    "        # 如果他能被多次访问到就是叶子\n",
    "        rec = set() # 记录是第几次被访问\n",
    "        leaves = set() # 记录是否是叶子\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return \n",
    "            if node.val in rec:\n",
    "                leaves.add(node.val)\n",
    "                return \n",
    "            rec.add(node.val)\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        \n",
    "        ans = 0\n",
    "        def getDepth(node, d):\n",
    "            nonlocal ans \n",
    "            if not node:\n",
    "                return\n",
    "            if node.val in leaves: # 是叶子节点更新逻辑\n",
    "                ans = max(ans, d)\n",
    "                return \n",
    "            getDepth(node.left,d + 1)\n",
    "            getDepth(node.right, d + 1)\n",
    "        getDepth(root, 0)\n",
    "            \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def heightOfTree(self, root: Optional[TreeNode]) -> int:\n",
    "        leaves = set()\n",
    "        visited = set()\n",
    "        x = None\n",
    "        def visit(root):\n",
    "            nonlocal x\n",
    "            if root in visited:\n",
    "                x = root\n",
    "                raise ValueError\n",
    "            visited.add(root)\n",
    "            if root.left:\n",
    "                visit(root.left)\n",
    "            else:\n",
    "                visit(root.right)\n",
    "        try:\n",
    "            visit(root)\n",
    "        except ValueError:\n",
    "            leaves.add(x)\n",
    "            while True:\n",
    "                x = x.left\n",
    "                if x in leaves:\n",
    "                    break\n",
    "                leaves.add(x)\n",
    "        ret = 0\n",
    "        def visit2(root, depth=0):\n",
    "            nonlocal ret\n",
    "            if root:\n",
    "              if root in leaves:\n",
    "                ret = max(ret, depth)\n",
    "              else:\n",
    "                visit2(root.left, depth+1)\n",
    "                visit2(root.right, depth+1)\n",
    "        visit2(root)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def heightOfTree(self, root: Optional[TreeNode]) -> int:\n",
    "        ss, ps = set(), set()\n",
    "        def dfs(node):\n",
    "            if node in ss:\n",
    "                ps.add(node)\n",
    "            else:\n",
    "                ss.add(node)\n",
    "                if node.left:\n",
    "                    dfs(node.left)\n",
    "                if node.right:\n",
    "                    dfs(node.right)\n",
    "\n",
    "        def dfs2(node,x):\n",
    "            if node:\n",
    "                if node in ps:\n",
    "                    self.res = max(self.res, x)\n",
    "                else:\n",
    "                    dfs2(node.left, x+1)\n",
    "                    dfs2(node.right, x+1)\n",
    "        dfs(root)\n",
    "        self.res = 0\n",
    "        dfs2(root, 0)\n",
    "        return self.res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
